import java.util.Arrays;

public class Leetcode1470 {

    private TreeNode parent;

    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        if (root == null) {
            parent.right = new TreeNode(val);
            return null;
        }

        if (root.val > val) {
            parent = root;
            insertIntoMaxTree(
                    root.right,
                    val
            );
            return root;
        }

        if (parent == null) {
            return new TreeNode(
                    val,
                    root,
                    null
            );

        } else {
            parent.right = new TreeNode(
                    val,
                    root,
                    null
            );


            return root;
        }
    }

    public TreeNode insertIntoMaxTree1(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }

        if (val > root.val) {
            return new TreeNode(
                    val,
                    root,
                    null
            );
        }

        root.right = insertIntoMaxTree1(
                root.right,
                val
        );

        return root;
    }


    public TreeNode insertIntoMaxTree2(TreeNode root, int val) {
            return null;
    }

}
